The scheduler for the enhanced uplink (EUL) schedules EUL traffic of multiple users. EUL serves as a counterpart to the high speed downlink packed access (HSDPA) service in the Wideband Code Division Multiple Access (WCDMA) downlink. Together, EUL and HSDPA provide the backbone for the mobile broadband for a WCDMA cellular system. The scheduler operates in a closed loop fashion, where transmission grants, i.e. control signals, are issued in response to transmission requests and air interface load (measurements). The third generation partnership project (3GPP) standard provides channels with certain associated capacity, range and delay properties. Notably, the control loop is dynamic, with nonlinear constraints and plenty of discrete ranges of various states.
In this context the load on the uplink is of central importance. The task of the scheduler is to schedule as much traffic as possible, at the same time as the uplink coverage and stability needs to be maintained. In case a too large amount of traffic is scheduled, the interference from other terminals can make it impossible for terminals at the cell edge to maintain communication—the coverage of the cell becomes too low. The cell may also become unstable in case too much traffic is scheduled. In order to avoid these two problems the scheduler schedules traffic under the constraint that the air interface load is held below a specific value. The load factor of a cell is defined as the fraction of the own cell uplink power, and the total uplink interference. The total uplink interference consists of the sum of the own cell power, the neighbor cell interference and the thermal noise floor. The load factor of a user is equivalently given by the quotient of the user power and the total wideband received power (P_u/P_RTWP).
Enhanced Uplink in WCDMA
The WCDMA enhanced uplink aims at scheduling traffic to times when the uplink interference situation is favorable, thereby utilizing air interface resources in a better way than before. The air interface load is measured by the noise rise, over the thermal level, a quantity denoted rise over thermal (RoT). This is illustrated in FIG. 1, which illustrates the air interface load. The pole capacity is the limiting theoretical bit rate of the uplink, corresponding to an infinite noise rise.
The uplink data channel is denoted E-DPDCH. This channel supports a high rate. It is however not involved in the scheduling control as such, this is the task of the corresponding control channel, denoted E-DPCCH. This channel e.g. carries rate requests (measurement signals) from the User equipments (UEs) to the EUL scheduler. There are also some downlink channels supporting EUL. The first of these is the E-AGCH channel which carries absolute grants (control signals) to each UE. More peripheral is the E-RGCH channel which carries relative grants (also control signals) from the radio base station node B to the UE. Finally, the E-HICH channel carries ACK/NACK information.
The grants mentioned above are the quantities signaled to the UE indicating what rate (actually power) it may use for its transmission. The UE can, but need not, use its complete grant. Relative grants are used to control the interference in neighbor cells—these can only decrease the current grant of the UE one step. It is stressed that there are only a discrete number of grant levels that can be used.
Scheduling in Enhanced Uplink
The task of the scheduler is to schedule EUL user traffic, to enhance user and cell capacity, at the same time as it:                Keeps track of the air interface cell load, avoiding over-scheduling that may cause cell instability and loss of coverage.        Keeps track of other available traffic, like transport resources and hardware.        Receives, measures and estimates quantities relevant for its scheduling operation.        Transmits orders to UEs, primarily in the form of granted power/bitrates.        
When doing this the scheduler needs to operate within the constraints induced by the 3GPP standard, these constraints being e.g.                Limited grant transmission capacity.        Grant transmission delays.        Grant step up rate limitations.        Standard limited UE status information.        
Conventional schedulers are designed with different objectives in mind. UEs are e.g. given the maximum rate as long as there are resources available, in an order defined by a priority list. Then, in case of lack of resources, overload handling is invoked. This overload handling reduces the priority of the UE with the best grant to a very low priority, thereby resulting in switching in case of conflicting high rate users. Since there is a dead time until re-scheduling takes effect, this results in a loss of capacity.
UEs in EUL Scheduling
The UEs form an integral part of the scheduling loop. In this case it is not the data transfer on the E-DPDCH channel that is of interest; rather it is the operation of the UE according to the 3GPP standard that is the focal point. The UE performs e.g. the following tasks:                Reception of absolute grants on the E-AGCH channel (control signal). There are 4 of these channels, however only one absolute grant can be transmitted per Transmission time Interval (TTI) on each channel.        Reception of relative grants on the E-RGCH channel (control signal). The relative grants can only reduce the scheduled grant of the UE by 1 step.        Formation of the scheduled grant of the UE, from the absolute and relative grants. The scheduled grant is the actual grant used by the UE for transmission.        Using the absolute grants and the relative grants, for computation of the power to be used for data transmission. This is expressed using beta factors that are computed as nonlinear functions of the scheduled grant, accounting also for the absolute output power level of the UE.        Transmission of user data, in accordance with the computed beta factor.        Determination and signaling of the happy bit (measurement signal) to the scheduler of the Radio Base Station (RBS). If not happy the UE requests a higher bit rate.        Determination and signaling of scheduled information (measurement signal) to the scheduler of the RBS. The scheduled information is based on the amount of data in the Radio Link Control (RLC) buffer, which allows the scheduler to make scheduling decisions for the UE.        Determination and signaling of the transport format used (E-TFCI). This carries e.g. the actual beta factor applied by the UE, thereby supporting the load estimator that provides the scheduler with information of the current air-interface load.        
UEs are divided into different categories depending on whether they support 10 ms TTIs (TTI is roughly the scheduling sampling period) only, or also 2 ms TTIs. Their maximal bit rates also affect the category of the UEs. The details appear in Table 1,
TABLE 1UE categories in EUL.PeakPeakE-DCHSupport forData Rate,Data Rate,categoryMinimum SF2 ms TTI10 ms TTI2 ms TTICategory 11 × SF4—0.73 Mbit/s—Category 22 × SF4γ1.46 Mbit/s1.46 Mbit/sCategory 32 × SF4—1.46 Mbit/s—Category 42 × SF2γ  2 Mbit/s 2.9 Mbit/sCategory 52 × SF2—  2 Mbit/s—Category 62 × SF4 +γ  2 Mbit/s5.76 Mbit/s2 × SF2Existing Formulation of the Scheduling Problem
In existing cellular systems, scheduling schemes are often designed in an ad hoc manner. This leads to suboptimal performance in terms of throughput and may manifest itself in problems with stability. A reason for the ad hoc design has been the difficulty in computing a solution in real time. A key to overcome this difficulty is to convert the problem to a problem involving maximization of a convex function over a convex polytope. A maximization of a convex function over a convex polytope will also be referred to as a convex maximization/optimization herein.
Further, several papers in the literature consider the problem of scheduling the transmission powers instead of grants, see e.g. Kumaran, K. and Qian, L. (2003), Uplink scheduling in CDMA packet-data systems, in ‘Proc. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM 2003)’, Vol. 1, pp. 292-300, Lau, V. and Kwok, Y.-K. (2004), ‘Performance analysis of SIMO space-time scheduling with convex utility function: zero-forcing linear processing’, IEEE Transactions on Vehicular Technology, 53(2), 339-350, Oh, S.-J. and Wasserman, K. (1999a), Adaptive resource allocation in power constrained CDMA mobile networks, in ‘Proc. 1999 IEEE Wireless Communications and Networking Conference’, Vol. 1, pp. 510-514, Oh, S.-J. and Wasserman, K. M. (1999b), Optimality of greedy power control and variable spreading gain in multi-class CDMA mobile networks, in ‘MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking’, ACM, New York, N.Y., USA, pp. 102-112, Oh, S.-J., Zhang, D. and Wasserman, K. (2003), ‘Optimal resource allocation in multiservice CDMA networks’, IEEE Transactions on Wireless Communications, 2(4), 811-821, Shu, T. and Niu, Z. (2003), A channel-adaptive and throughput-efficient scheduling scheme in voice/data DS-CDMA networks with constrained transmission power, in ‘Proc. 2003 IEEE International Conference on Communications (ICC '03)’, Vol. 3, pp. 2229-2233, Zhang, D., Oh, S.-J. and Bhushan, N. (2007), ‘Optimal resource allocation for data service in CDMA reverse link’, IEEE Transactions on Wireless Communications, 6(10), 3648-3656, Zhang, D., Sambhwani, S. and Mohanty, B. (2008), HSUPA scheduling algorithms utilizing RoT measurements and interference cancellations, in ‘Proc. 2008 IEEE International Conference on Communications (ICC '08)’, pp. 5033-5037.
A typical basic formulation involves maximizing the throughput subject to power saturation limits at the UEs. This requires that the channel gains from the UEs to the Node B be known by the scheduler. The algorithms in these papers typically involve greedy-type strategies. In some cases, the problem of optimizing with respect to the scheduled interference is dealt with by generating a number of candidate (greedy) solutions (each with a different total interference), and then selecting the best one.
In Kumaran and Qian (2003), the problem of scheduling the transmission powers of the users to maximize total throughput is considered. The problem formulation includes constraints on the transmission power of each user as well as a constraint to ensure feasibility. It is assumed that the channel gains are known, and hence that the constraints on the transmission powers can be converted to constraints on the received powers. The throughput is expressed as a weighted sum of user rates, where the weights are chosen to ensure queue stability (boundedness of queue lengths).
The resulting solution has the property that each user transmits at full power or not at all. For a certain given level of interference, the scheduling algorithm in Kumaran and Qian (2003) involves ordering the users according to a particular ranking metric and then allocating full power to the user with the highest ranking. The remaining users are then re-ordered to take into account the previous allocation. The process of re-ordering and allocating to the highest ranking user is repeated until the scheduled interference equals the given level interference. The optimal level of interference is determined by performing the preceding algorithm for a number of allowable interference levels, and then selecting the best one.
In Zhang (2008), a scheduling algorithm which allows a tradeoff between throughput and fairness is described. The algorithm involves sorting the users according to the following priority metric:
      Priority    ⁡          (      k      )        =                    [                              r            req                    ⁡                      (            k            )                          ]                    1        /        β                            r        ~            ⁡              (        k        )            where {tilde over (r)}(k) is the filtered throughput for the user, rreq(k) is the rate requested by the user and β is a parameter, which determines the relative degree of fairness between the users. Rate allocation is then done by greedy filling the available load starting from the user with the highest priority. This implies that each user transmits at their requested rate or not at all. The algorithm has the property that it maximizes a function which is closely related to the total throughput.
The existing technologies for scheduling are associated with a number of disadvantages and problems, such as non-optimal throughput, risk for instability, and a risk for coverage loss.
Hence there exist a need for new methods and devices providing improved scheduling in cellular radio systems, in particular WCDMA systems.